package com.atguigu.dp;

//4.斐波那契数列 - 终极优化
public class Demo04 {
    public static void main(String[] args) {
        for(int i = 0 ; i<=100 ; i++){
            System.out.println(i+"  :  " + fn(i));
        }
    }

    public static long fn(int n){
        long num2 = 0 ;    // n-2
        long num1 = 1 ;    // n-1
        if(n==0){
            return 0;
        }
        if(n==1){
            return 1 ;
        }

        for(int i = 2 ; i<=n ;i++){
            long result = num2 + num1 ;
            num2 = num1 ;
            num1 = result ;
        }
        return num1;
    }


}
